package anthology.daily_question._24_12;

import java.util.*;

//https://leetcode.cn/problems/reduce-array-size-to-the-half/description/?envType=daily-question&envId=2024-12-15
public class _1338数组大小减半 {
    class Solution {
        public int minSetSize(int[] arr) {
            Map<Integer, Integer> freq = new HashMap<>();
            for (int num : arr) {
                freq.put(num, freq.getOrDefault(num, 0) + 1);
            }

            List<Integer> occ = new ArrayList<>(freq.values());
            Collections.sort(occ, Collections.reverseOrder());
            int cnt = 0, ans = 0;
            for (int c : occ) {
                cnt += c;
                ans += 1;
                if (cnt * 2 >= arr.length) {
                    break;
                }
            }
            return ans;
        }
    }
}
